package Heap;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * P2099 找到和最大的长度为 K 的子序列
 */
public class P2099 {
}
/**
 * 数组排序
 * */
class P2099Test01{
    public int[] maxSubsequence(int[] nums, int k) {
        Arrays.sort(nums);
        int len=nums.length;
        int[] ans=new int[k];
        while(k>0){
            ans[k-1]=nums[len-1];
            k--;
            len--;
        }

        return ans;
    }
}

/**
 * 优先队列
 * */
class P2099Test02{

    private class T{
        int index;
        int num;

        public T(int index, int num) {
            this.index = index;
            this.num = num;
        }

        public int getIndex() {
            return index;
        }

        public int getNum() {
            return num;
        }
    }

    private class CompareT implements Comparator<T> {
        @Override
        public int compare(T o1, T o2) {
            return o2.getNum()-o1.getNum();
        }
    }

    public int[] maxSubsequence(int[] nums, int k) {
        PriorityQueue<T> queue=new PriorityQueue<>(new CompareT());
        for(int i=0;i<nums.length;i++){
            queue.add(new T(i, nums[i]));
        }

        int[] ans=new int[k];
        int[] index=new int[k];
        for(int i=0;i<k;i++){
            index[i]=queue.poll().getIndex();
        }
        Arrays.sort(index);

        for(int i=0;i<k;i++){
            ans[i]=nums[index[i]];
        }

        return ans;
    }
}

